#include "huffman.h"

#ifdef HUFFMAN_SHORT

struct NODE_T *pool;
NODE *qqq, *q;
int n_nodes = 0, qEnd = 1;
char **code, buf[BYTES];
unsigned int *freq = NULL;
int max, lenght;

NODE newNodeShortHuffmanTree(int freq, short c, NODE a, NODE b) {

	NODE n = pool + n_nodes++;
    n->c = -1;

	if (freq) n->c = c, n->freq = freq;
	else {
		n->left = a, n->right = b;
		n->freq = a->freq + b->freq;
	}

	return n;
}

void qInsertShortHuffmanTree(NODE n) {
	int j, i = qEnd++;

	while ((j = i / 2)) {
		if (q[j]->freq <= n->freq) break;
		q[i] = q[j], i = j;
	}

	q[i] = n;
}

NODE qRemoveShortHuffmanTree(){
    int i, l;
	NODE n = q[i = 1];

	if (qEnd < 2)
        return 0;

	qEnd--;
	while ((l = i * 2) < qEnd) {
		if (l + 1 < qEnd && q[l + 1]->freq < q[l]->freq) l++;
		q[i] = q[l], i = l;
	}

	q[i] = q[qEnd];

	return n;
}

void buildCodeShortHuffmanTree(NODE n, char *s, int len){
    static char *out = buf;

	if ( n->c != -1 ) {
		s[len] = '\0';
		strcpy(out, s);
#ifdef DEBUG
#endif
		code[n->c] = out;
		out += len + 1;
		return;
	}

	s[len] = '0'; buildCodeShortHuffmanTree(n->left,  s, len + 1);
	s[len] = '1'; buildCodeShortHuffmanTree(n->right, s, len + 1);
}

int initShortHuffmanTree(const short *s,int size) {
	char c[16];

    int i;
    max = s[0];
    for(i=1;i<size;i++)
        if( s[i] > max)
            max = s[i];

    max++;
	lenght = size;
	
    freq = (unsigned int *)malloc(max*sizeof(unsigned int));
    for (i = 0; i < max; i++)
        freq[i] = 0;

    pool = (struct NODE_T *)malloc(sizeof(struct NODE_T)*size);
    qqq = (NODE *)malloc(sizeof(NODE)*(size-1));
    q = qqq-1;
    code = (char **)malloc(sizeof(char)*size);
    for (i = 0; i < max; i++){
        code[i] = (char *)malloc(sizeof(char)*BYTES);
        code[i][0] = '\0';
    }
    i = 0;
	while (i < size){
        freq[s[i]]++;
        i++;
    }

	for (i = 0; i < max; i++)
		if (freq[i]){
#ifdef DEBUG
            printf("%d %d\n",i,freq[i]);
#endif
            qInsertShortHuffmanTree(newNodeShortHuffmanTree(freq[i], i, 0, 0));
        }
	while (qEnd > 2)
		qInsertShortHuffmanTree(newNodeShortHuffmanTree(0, 0, qRemoveShortHuffmanTree(), qRemoveShortHuffmanTree()));

	buildCodeShortHuffmanTree(q[1], c, 0);

	return max;
}

void encode(const char *s, char *out){
	while (*s) {
		strcpy(out, code[(int)*s]);
		out += strlen(code[(int)*s++]);
	}
}

NODE decode(const char *s){
	
	NODE t = q[1];	
	NODE n = t;
	
	while (*s) {
		if (*s++ == '0') n = n->left;
		else n = n->right;
	}

	return (t != n)? n:NULL;	
}

void saveHuffmanFrequency(FILE *save){
	
	fwrite(&max,sizeof(int),1,save);
	fwrite(&lenght,sizeof(int),1,save);
	
	int i;
	for (i = 0; i < max; i++){
#ifdef DEBUG
            printf("%d %d\n",i,freq[i]);
#endif
	}

#ifdef DEBUG
	for (i = 0; i < max; i++)
        if(code[i])
            printf("%d: %s\n", i, code[i]);
#endif

	int x = fwrite(freq,sizeof(unsigned int),max,save);
    while( x < max)
        x += fwrite(freq+x,sizeof(unsigned int),max,save);
}

void readHuffmanFrequency(FILE *load,FREQUENCY_SAVE saves){
    int i;
	
	fread(&max,sizeof(int),1,load);
	fread(&lenght,sizeof(int),1,load);

#ifdef DEBUG
	printf("max: %d size: %d\n",max,lenght);
#endif	

	freq = (unsigned int *)malloc(sizeof(unsigned int)*max);
	int x = fread(freq,sizeof(unsigned int),max,load);
	
#ifdef DEBUG	
	printf("%d\n",x);	    
#endif
	
	while( x < max){
        x += fread(freq+x,sizeof(int),max,load);	    
	}

    int size = lenght;    
    pool = (struct NODE_T *)malloc(sizeof(struct NODE_T)*size);
    qqq = (NODE *)malloc(sizeof(NODE)*(size-1));
    q = qqq-1;
    code = (char **)malloc(sizeof(char)*max);
    
    for (i = 0; i < max; i++){
        code[i] = (char *)malloc(sizeof(char)*BYTES);
        code[i][0] = '\0';
    }

    i = 0;	
	for (i = 0; i < max; i++)
		if (freq[i]){
#ifdef DEBUG
            printf("%d %u\n",i,freq[i]);
#endif
            qInsertShortHuffmanTree(newNodeShortHuffmanTree(freq[i], i, 0, 0));
        }

	while (qEnd > 2)
		qInsertShortHuffmanTree(newNodeShortHuffmanTree(0, 0, qRemoveShortHuffmanTree(), qRemoveShortHuffmanTree()));
	
	char c[16];
	buildCodeShortHuffmanTree(q[1], c, 0);

#ifdef DEBUG
	for (i = 0; i < max; i++)
        if(code[i])
            printf("HUFFMAN %d: %s %d\n", i, code[i],freq[i]);
#endif
}

#else

struct NODE_T pool[BYTES] = {{0}};
NODE qqq[BYTES-1], *q = qqq - 1;
int n_nodes = 0, qEnd = 1;
char *code[BYTES/2] = {0}, buf[BYTES*6];

NODE newNode(int freq, char c, NODE a, NODE b) {
    NODE n = pool + n_nodes++;

    if (freq) n->c = c, n->freq = freq;
    else {
        n->left = a, n->right = b;
        n->freq = a->freq + b->freq;
    }
    return n;
}

void qInsert(NODE n) {

	int j, i = qEnd++;

	while ((j = i / 2)) {
		if (q[j]->freq <= n->freq) break;
		q[i] = q[j], i = j;
	}

	q[i] = n;
}

NODE qRemove(){
	int i, l;
	NODE n = q[i = 1];

	if (qEnd < 2)
        return 0;

	qEnd--;
	while ((l = i * 2) < qEnd) {
		if (l + 1 < qEnd && q[l + 1]->freq < q[l]->freq) l++;
		q[i] = q[l], i = l;
	}

	q[i] = q[qEnd];

	return n;
}

void buildCode(NODE n, char *s, int len) {
	static char *out = buf;

	if (n->c) {
		s[len] = 0;
		strcpy(out, s);
		code[(int)n->c] = out;
		out += len + 1;
		return;
	}

	s[len] = '0'; buildCode(n->left,  s, len + 1);
	s[len] = '1'; buildCode(n->right, s, len + 1);
}

void init(const char *s) {
	int i, freq[BYTES/2] = {0};
	char c[16];

	while (*s) freq[(int)*s++]++;

	for (i = 0; i < BYTES/2; i++)
		if (freq[i]) qInsert(newNode(freq[i], i, 0, 0));

	while (qEnd > 2)
		qInsert(newNode(0, 0, qRemove(), qRemove()));

	buildCode(q[1], c, 0);
}

void encode(const char *s, char *out){
	while (*s) {
		strcpy(out, code[(int)*s]);
		out += strlen(code[(int)*s++]);
	}
}

void decode(const char *s, NODE t){
	NODE n = t;
	while (*s) {
		if (*s++ == '0') n = n->left;
		else n = n->right;

		if (n->c) putchar(n->c), n = t;
	}

	putchar('\n');
	if (t != n) printf("garbage input\n");
}

#endif






